class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    bool hasPath(vector<vector<char> >& matrix, string word) {
        int i, j;
        int m = matrix.size();
        int n = matrix[0].size();
        for(i = 0; i < m; i++) {
            for(j = 0; j < n; j++)
                if(matrix[i][j]==word[0]) {
                    if(backtrack(matrix, word, 0, i, j))
                        return true;
            }
        }
        return false;
    }
    bool backtrack(vector<vector<char>>& matrix, string& word, int idx, int x, int y) {
        int newx, newy;
        int m = matrix.size();
        int n = matrix[0].size();
        if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y]!=word[idx])
            return false;
        if(idx == word.size()-1) return true;
        char tmp = matrix[x][y];
        matrix[x][y] = '#';
        for(int i = 0; i < 4; i++) {
            newx = x + dx[i];
            newy = y + dy[i];
            if(backtrack(matrix, word, idx + 1, newx, newy)) return true;
        }
        matrix[x][y] = tmp;
        return false;
    }
};